%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------

\documentclass{beamer}

\mode<presentation> {
\usetheme{Madrid} % very very good
}

\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
\usepackage{pgf,pgfpages}
\usepackage{units}
\usepackage{listings}
\usepackage[utf8]{inputenc}

\usepackage[variablett]{lmodern}

\lstset{ %
  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
%  basicstyle=\footnotesize,        % the size of the fonts that are used for the code
  language=C++,
%  basicstyle=\ttfamily,
  basicstyle=\ttfamily\scriptsize,
  keywordstyle=\color{blue}\ttfamily,
  stringstyle=\color{red}\ttfamily,
  commentstyle=\color{darkgreen}\ttfamily,
  breaklines=true,
  columns=flexible,
  literate={_}{\textsmallunderscore}1,
%  gobble=4,
%  xleftmargin=\leftmargini, 
%  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{green},      % comment style
  deletekeywords={...},            % if you want to delete keywords from the given language
  extendedchars=true,              
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 
  keywordstyle=\color{blue},       % keyword style
  morekeywords={*,function, foreach, procedure, put, pop, remove,...},
  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{black}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showstringspaces=false,          % underline spaces within strings only
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
%  stringstyle=\color{mauve},    	% string literal style
%  tabsize=4,                       % sets default tabsize to 2 spaces 
  title=\lstname,                   % show the filename of files included with \lstinputlisting; also try caption instead of title
  mathescape=true
}



%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title[Short title]{Implémentation de MaxRPWC1} % The short title appears at the bottom of every slide, the full title is only on the title page
\vspace{0.2cm}
\vspace{0.2cm}
\author{
Etudiant: KHONG Minh Thanh\\
Superviseurs: Yves Deville, Jean-Baptiste Mairy
\vspace{0.4cm}
}

\institute{
Institut de la Francophonie pour l'Informatique \\
\& beCool Constraints Group, ICTEAM/INGI, UCL
}
\begin{document}

\begin{frame}
\titlepage % Print the title page as the first slide
\end{frame}

\begin{frame}
\frametitle{Overview} % Table of contents slide, comment this block out to remove it
\tableofcontents % Throughout your presentation, if you choose to use \section{} and \subsection{} commands, these will automatically be printed on this slide as an overview of your presentation
\end{frame}

%----------------------------------------------------------------------------------------
%	PRESENTATION SLIDES
%----------------------------------------------------------------------------------------

%------------------------------------------------
\section{MaxRPWC1} 
%------------------------------------------------
\begin{frame}[fragile]
\frametitle{Max-RPWC-1}
Algorithme MaxRPWC1 \cite{domain:2008} 
\begin{lstlisting}[caption=function Revise of Max-RPWC-1]
function Revise($x_j, c_i,MaxRPWC$)
   for each value $a \in D(x_j)$
      PW $\leftarrow$ FALSE;
      foreach valid $\tau (\in rel(c_i)) \geq_l lastGAC_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
         PW $\leftarrow$ TRUE;
         for each $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
            if $\nexists$ valid $\tau' (\in rel(c_m))$ s.t. $\tau[vars(c_i) \cap vars(c_m)] = \tau' [vars(c_i) \cap vars(c_m)]$
               PW $\leftarrow$ FALSE; break;
         if PW = TRUE $lastGAC_{x_j,a,c_i} \leftarrow \tau$; break;
      if PW = FALSE remove $a$ from $D(x_j)$;
   return number of deleted values;
\end{lstlisting}
{\footnotesize
Ligne 4-10 : pour chaque valide tuple $\tau \in rel(c_m), \tau[x_j]=a$, tester s'il peut étendre aux autres contraintes intersectées avec $c_i$. Si non, enlever $a$ de $D(x_j)$.\\
Ligne 6-7 : pour chaque contrainte $c_m$, tester si $\tau$ a PW-support $\tau'$ dans $c_m$.\\
Complexité : time : $O(e^2k^2d^p)$, space : $O(ekd)$, p : maximum nombre de variables dans deux contraintes intersectées

}
\end{frame}

%------------------------------------------------

%%------------------------------------------------
%\section{MaxRPWC}
%%------------------------------------------------
%\begin{frame}
%\frametitle{MaxRPWC}
%\begin{itemize}
%\item L'algorithme MaxRPWC est implémenter par deux classes : \textit{MaxRPWC} et \textit{ConstraintHardExtensionRPWC}.
%
%\item La classe \textit{MaxRPWC} étend la classe \textit{AC}. Quand la propagation \textit{MaxRPWC} est créée, elle va trouver les intersections entre les contrainte de type \textit{ConstraintHardExtensionRPWC} et les ajouter dans ces contraintes.
%
%\item La classe \textit{ConstraintHardExtensionRPWC} implémente la méthode \textit{runPropagator(Variable)} qui est sollicitée pour la propagation.
%
%\end{itemize}
%
%\end{frame}
%
%%------------------------------------------------
%
%\begin{frame}[fragile]
%\frametitle{MaxRPWC}
%\textit{ConstraintHardExtensionRPWC.runPropagator(Variable)}
%\begin{lstlisting} [caption= méthode runPropagator()]
%Propagation.propagate()
%// OUT : enlever les tuples invalides, ne pas étendre aux autres tuples, 
%//        les valeurs inconsistantes du domaine de variable
%  Prendre les intersections a tester
%     Pour chaque tuple $\tau$ dans les intersections
%       Si $\tau$ est invalide ou $\tau$ ne peut pas etendre aux autres tuples
%          Enlever $\tau$
%     Mettre a jours le domaine des variables
%\end{lstlisting}
%\end{frame}
%%------------------------------------------------
%
%------------------------------------------------
\section{Implémentation}
%------------------------------------------------
\begin{frame}
\frametitle{Implémentation}
Il y a deux classes principale à faire :
\begin{itemize}
\item MaxRPWC3 : 
	\begin{itemize}
	\item appeler la propagation 
	\item trouver les intersections entre les contraintes
	\end{itemize}
\item ConstraintHardExtensionRPWC3 :
	\begin{itemize}
	\item contenir la méthode "runPropagator(Variable)" qui fait la fonction "Revise($x_j, c_i,MaxRPWC$)" pour réviser la consistance des variables de la contrainte
	\end{itemize}
\end{itemize}
\end{frame}

%------------------------------------------------

\begin{frame}[fragile]
\frametitle{Implémentation}
Implémentation de la méthode "runPropagator(Variable)" :
\begin{lstlisting}[caption=function runPropagator(Variable)]
ConstraintHardExtensionRPWC3.runPropagator(Variable)
   // $c_i$ is this constraint
   for each variable $x_j \in c_i$ 
      Revise($x_j, c_i,MaxRPWC$)
   // update domain of all variable in $c_i$, return false if a domain of variable is empty   
   return updateDomain()
\end{lstlisting}
\begin{itemize}
\item Problème : 
Ne pas implémenter $lastGAC_{x_j,a,c_i}$ à cause du changement des indexes des tuples, on doit donc chaque fois parcourir au début des tuples.
\item Modification : 
Enlever les tuples qui ne peut pas étendre aux autres tuples dans la fonction "Revise($x_j, c_i,MaxRPWC$)", il diminue les tuples à parcourir chaque fois
\end{itemize}


\end{frame}

%------------------------------------------------
\section{Expérimentation}
%------------------------------------------------
\begin{frame}
\frametitle{Expérimentation}
\begin{itemize}
\item L'expérimentation est lancé sur un PC de 4GB RAM, Core i5-2520M, Ubuntu. 
\item Le problème utilisé est Renault dans \cite{problem}. Le nombre de variable intersecté est 2-10.
\item Les consistances à tester sont GAC(algo STR2), PWC+GAC et MaxRPWC1.
\item Les critères à considérer sont CPU time(s), et node.
\end{itemize}
\end{frame}
%------------------------------------------------

\begin{frame}
\frametitle{Expérimentation}
Le résultat (CPU time, node) sur le problème modifiedRenault :
\begin{center}
    \begin{tabular}{ | l | l | p{2cm} | p{2cm} | p{2.3cm} |}
    \hline
    Problème & intersection & GAC & PWC+GAC & MaxRPWC1\\ \hline
    Renault-1 & 2575 & \textbf{1.436}, 972 & 2.116, \textbf{0} & 5.356, \textbf{0}\\ \hline
    Renault-2 & 2569 & \textbf{0.768}, \textbf{111} & 2.011, \textbf{111} & 6.562, \textbf{111}\\ \hline
    Renault-3 & 2573 & \textbf{1.593}, 1121 & 1.805, \textbf{0} & 48.973, 1052\\ \hline
    Renault-4 & 2571 & \textbf{0.727}, 114 & 3.380, \textbf{112} & 7.527, \textbf{112}\\ \hline
    Renault-5 & 2573 & 1.676, 1299 & \textbf{1.655, 0} & 58.959, 1136\\ \hline
    Renault-6 & 2571 & \textbf{1.677}, 1379 & 3.238, 1256 & 54.595, \textbf{1139}\\ \hline
    Renault-7 & 2572 & \textbf{0.897}, 141 & 2.674, \textbf{112} & 7.653, 113\\ \hline
    Renault-8 & 2571 & \textbf{1.609}, 1124 & 1.652, 0 & 51.019, \textbf{1060}\\ \hline
    Renault-9 & 2573 & \textbf{0.802}, 155 & 2.474, \textbf{111} & 7.773, 115\\ \hline
    Renault-10 & 2593 & \textbf{2.142}, 1459  & 4.277, 1430 & 42.766, \textbf{1190}\\ \hline
    \end{tabular}
\end{center}
\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Expérimentation}
Remarque :
\begin{itemize}
\item Le MaxRPWC1 est plus lente car il n'est pas optimale, le temps de propagation est chère.
\item Dans tous les problèmes, les nodes de PWC+GAC et MaxRPWC1 sont plus petites que celles de GAC qui correspond la théorie.
\item Le temps d'exécution de PWC+GAC et MaxRPWC1 est plus long que celui de GAC, car leur propagation est plus coûteuse.
%\item Dans certains problèmes, PWC+GAC et MaxRPWC1 peuvent détecter
\end{itemize}

\end{frame}

%------------------------------------------------

%------------------------------------------------
\section{Perspective}
%------------------------------------------------
\begin{frame}
\frametitle{Perspective}
\begin{itemize}
\item Résoudre le problème de $lastGAC_{x_j,a,c_i}$
\item Implémenter MaxRPWC3 qui est promis en pratique en comparaison avec MaxRPWC1
\item Question : Quel méthode est plus efficace si on parcours :
\begin{itemize}
\item d'abord les valeurs de variable, ensuite les tuples
\item ou d'abord les tuples, ensuite les valeurs (ex: comme STR1) ?
\end{itemize}  
\end{itemize}

\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{References}
\footnotesize{
\begin{thebibliography}{99} % Beamer does not support BibTeX so references must be inserted manually as below
\bibitem{domain:2008} Bessiere, Christian, Kostas Stergiou, and Toby Walsh. "Domain filtering consistencies for non-binary constraints." Artificial Intelligence 172.6 (2008): 800-822.
\bibitem{problem} http://www.cril.univ-artois.fr/lecoutre/benchmarks.html
\end{thebibliography}
}
\end{frame}

%------------------------------------------------

\begin{frame}
\Huge{\centerline{The End}}
\end{frame}

%----------------------------------------------------------------------------------------

\end{document} 